package 链表和树.链表.digui;

import java.util.PriorityQueue;

//Java：合并 K 个升序链表
public class MergeKSortedLists{
    public static void main(String[] args) {
        Solution solution = new MergeKSortedLists().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
class Solution {
        //初始把链表的头节点入堆，然后不断地弹出堆中最小的节点x，
        // 如果x.next有值那么就加入堆中因为合并以后的第二个节点可能是头节点也可能是节点的下一个节点
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        //这表示创建一个优先队列，其中：
        //队列中的元素按val值从小到大排序（最小堆）当然堆的样子是二叉树结构
        //每次取出元素时，总是取出val值最小的节点
        for (ListNode head : lists) {
            if(head != null){
                pq.offer(head);//把所有链表的头节点加入堆
            }
        }

        ListNode dummy = new ListNode();
        //都指向内存中的同一个 ListNode 对象
        ListNode cur = dummy;
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            if(node.next != null){
                pq.offer(node.next);
            }
            cur.next = node;
            cur = cur.next;//更新位置链接下一个节点
        }
        return dummy.next;
    }

    //TODO递归方法就绪中。。。。
}
//leetcode submit region end(Prohibit modification and deletion)

}